package array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 串联所有单词的子串_30 {
    public List<Integer> findSubstring(String s, String[] words) {
        int stepLength = words[0].length();
        int stepCnt = words.length;
        int windowLength = stepLength * stepCnt;
        Map<String, Integer> wordCntMap = new HashMap<>();
        for (String word : words) {
            wordCntMap.put(word, wordCntMap.getOrDefault(word, 0) + 1);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < stepLength; i++) {// 多起点  0 - （步长 -1） 都是起点  否则如   sfoothebarf这种会跳过
            Map<String, Integer> cntMap = new HashMap<>();
            // 每个起点开始 每次后移stepLength  如果距离已经到达了window  就删一个 加一个  判断两个map是否相等
            //                                          没到达window      就一直向windowput
            //  最后判断两个map是否相等
            for (int j = i; j <= s.length() - stepLength; j += stepLength) {  // 下一个单词  j -> j + stepLength -1  因此是 j <=  而不是  <
                // window满后 窗口后移之后移除之前的单词
                if (j >= i + windowLength) {
                    String prev = s.substring(j - windowLength, j - windowLength + stepLength);
                    Integer cnt = cntMap.get(prev);
                    if (cnt == 1) cntMap.remove(prev);
                    else cntMap.put(prev, cnt - 1);
                }
                String newWord = s.substring(j, j + stepLength);
                cntMap.put(newWord, cntMap.getOrDefault(newWord, 0) + 1);

                if (wordCntMap.equals(cntMap)) {
                    res.add(j - windowLength + stepLength);
                }
            }
        }
        return res;
    }
}
        